\section{唯一析因定理}

\begin{frame}{唯一析因定理}
  \begin{theorem}%定理1
[算术基本定理(fundamental theorem of arithmetic), 整数唯一析因定理)]
任一整数 $n$ ($\neq 0, \pm 1$) 可写为有限个素数之积， 且写法是唯一的（不计素数次序和正负号). 也就是说， $n$ 可写为
\begin{equation*}
n=p_{1} p_{2} \cdots p_{t} \tag{1}
\end{equation*}
其中 $p_{1}, p_{2}, \cdots, p_{t}$ 为素数。
\end{theorem}

\pause
在定理 1 中， “$n$ 唯一地写为素数之积”被称为 $n$ 的 \emph{(唯一素) 因子分解}， 或\emph{唯一析因} (unique factorization). 
\pause
将相同的素数因子乘在一起， 正负号提到前面， 则非零整数 $n$ 的素因子分解可写为
\begin{equation*}
n=(-1)^{\varepsilon} p_{1}^{v_{1}} p_{2}^{v_{2}} \cdots p_{r}^{v_{r}} \tag{2}
\end{equation*}
其中 $p_{1}, \cdots, p_{r}$ 为互异(正)素数， $v_{i}$ 是正整数， $\varepsilon=0$ 或 $1$. 
\pause
$n$ 的因子分解式也可写为
\begin{equation*}
n=(-1)^{\varepsilon} \prod_{p} p^{v_{p}} \tag{3}
\end{equation*}
其中 $p$ 遍历(正)素数， $v_{p}$ 是非负整数且只对有限多个 $p$ 取值非零 (约定 $p^{0}=1$. 故上述乘积是有限的). 
\pause
$v_{p}$ 也写为 $v_{p}(n)$ 或 $\operatorname{ord}_{p}(n)$, 是使得 $p^{r} \mid n$ 的最大整数 $r$, 称为 $n$ 在 $p$ 的\emph{指数} (exponent) 或\emph{阶}。 此时记为 $p^{v_{p}}~\|~n$, 符号 $\|$ 读为\emph{恰整除}。

\pause
用这种符号可知： $n \mid m$ 当且仅当 $v_{p}(n) \leqslant v_{p}(m)$ (对任意素数 $p$);
对正整数，$n = m$ 当且仅当 $v_{p}(n) = v_{p}(m)$ (对任意素数 $p$).
\end{frame}

\begin{frame}
  \begin{lemma}%引理1
  (1) 设 $p$ 为素数， 且 $p \nmid a$, 则 $(p, a)=1$.

 (2) 设 $p$ 为素数， $a, b$ 为整数。 若 $p \mid a b$, 则 $p \mid a$ 或 $p \mid b$.
 \end{lemma}

 \pause
 \begin{proof}
   (1) 因 $(p, a) \mid p$, 故 $(p, a)=p$ 或 $1$. 前者意味着 $p \mid a$, 不合条件。 故
   $(p, a)=1$.

  (2) 若 $p \nmid a$, 则 $(p, a)=1$, 有整数 $u, v$ 使 $u p+v a=1, u p b+v a b=b, p \mid$ 左边， 故 $p \mid b$.
\end{proof}

\pause
 \begin{proof*}[定理 1 的证明] 分解的存在性已证 (\S1.1 引理 1), 现证唯一性。 若有两种分解
 \[
 \begin{gathered}
    p_{1} p_{2} \cdots p_{t}=n=q_{1} q_{2} \cdots q_{s},\quad \text{则} \\
    p_{t} \mid q_{1} q_{2} \cdots q_{s}=\left(q_{1} q_{2} \cdots q_{s-1}\right) q_{s}.
 \end{gathered}
 \]
 由本节引理 1(2) 知， 若 $p_{t} \nmid q_{s}$, 则 $p_{t} \mid q_{1} q_{2} \cdots q_{s-1}$. 继而可知， 若 $p_{t} \nmid q_{s-1}$, 则 $p_{t} \mid q_{1} \cdots q_{s-2}$. 如此继续讨论可知， $p_{t} \mid q_{i}$ 必对某 $i$ 成立， 不妨设为 $p_{t} \mid q_{s}$ (可重排 $q_{1}, \cdots, q_{s}$ 的下标顺序). 而因 $q_{s}$ 为素数， 只有平凡因子， 故知 $p_{t}= \pm q_{s}$. 从上述两种分解的等式中消去 $p_{t}= \pm q_{s}$, 得
 \[
 p_{1} p_{2} \cdots p_{t-1}= \pm q_{1} q_{2} \cdots q_{s-1}
 \]
 如此继续进行， 不断消去素数因子， 必会有一方化为 $\pm 1$, 此时另一方也只能是 $\pm 1$, 故 $t=s, p_{i}=q_{i}$ ($i=1, \cdots, t$. 不计正负号和素数排列顺序). 定理得证。
 \end{proof*}
 \end{frame}

  \begin{frame}
    
    \begin{example}%例1
    $\sqrt{2}$ 不是有理数。
\end{example}

\pause
\begin{proof}
 用反证法。 假若 $\sqrt{2}$ 是有理数， 则可写为 $\sqrt{2}=a / b$ ($a, b$ 为互素整数).于是
 \[
 2=a^{2} / b^{2}, \quad 2 b^{2}=a^{2}
 \]
 由此可知 $2 \mid a^{2}$, 故 $2 \mid a$. 设 $a=2 a_{1}$ ($a_{1}$ 为整数), 代人则 $2 b^{2}=4 a_{1}^{2}, b^{2}=2 a_{1}^{2}$. 由此可知 $2 \mid b^{2}$, 故 $2 \mid b$. 与 $a, b$ 互素矛盾。
 \end{proof}

 \pause
 \begin{theorem}%定理3
   [Euclid 定理] 素数的个数是无穷的。
 \end{theorem}

 \pause
 \begin{proof}
   用反证法。 假设正素数只有有限多个， 设为 $p_{1}, \cdots, p_{s}$. 令 $N= p_{1} \cdots p_{s}+1$, 则 $N \geqslant 3$, 必有一个正素数因子 $p$ (由 $N$ 的素因子分解). 
   因此$p=p_{i}$, 对某个$1\leqslant i\leqslant s$.
   但$p_i$除$N$余$1$, 矛盾了。 定理得证。
\end{proof}
\end{frame}


 \begin{frame}
   \begin{definition}%定义1
     [最小公倍] 
     设 $a_{1}, \cdots, a_{s}$ 为非零整数， 若整数 $M$ 是所有 $a_{i}$ 的倍数 $(i=1, \cdots, s)$, 则称 $M$ 是 $a_{1}, \cdots, a_{s}$ 的\emph{公倍数}。 
     最小的正公倍数 $M_{0}$, 称为\emph{最小公倍数} (或\emph{最小公倍}， least common multiple, 简写为 $\mathrm{lcm}$ ), 记为 $\left[a_{1}, \cdots, a_{s}\right]$.
 \end{definition}

 \pause
 \begin{lemma}%引理2
 (1) 任意公倍数 $M$ 必是最小公倍数 $M_{0}$ 的倍数。

 (2) $\left[a_{1}, \cdots, a_{s-1}, a_{s}\right]=\left[\left[a_{1}, \cdots, a_{s-1}\right], a_{s}\right]$.
 \end{lemma}

 \pause
 \begin{theorem}%定理2
 设非零整数 $m, n$ 的唯一素因子分解分别为
 \[
 m=(-1)^{e} \prod_{p} p^{u_{p}}, \quad n=(-1)^{s} \prod_{p} p^{v_{p}}
 \]
 其中 $p$ 取遍正素数， $u_{p}, v_{p}$ 为非负整数且均只对有限个 $p$ 取值非零。 
\pause
 那么
 \[
 (m, n)=\prod_{p} p^{d_{p}}, \quad[m, n]=\prod_{p} p^{M_{p}}, \quad(m, n)[m, n]=|m n|,
 \]
 其中 $d_{p}=\min \left\{u_{p}, v_{p}\right\}, M_{p}=\max \left\{u_{p}, v_{p}\right\}$. 
 从而 $m, n$ 的公倍数恰为 $[m, n]$ 的倍数。
 \end{theorem}

\end{frame}

\begin{frame}
  例如， $60=2^{2} \cdot 3\cdot 5, 18=2 \cdot 3^{2}$, 故 
\pause
  $(60,18)=2 \cdot 3=6,[60,18]=2^{2} \cdot 3^{2}\cdot 5=180$.
  \pause
  再求$(60,18,5), [60,18,5]$ (分解，或辗转递归求解)。

  \pause
  \begin{proof*}[引理2的证明]
   (1) 做带余除法 $M=M_{0} q+r, 0 \leqslant r<M_{0}$, 则 $r=M-M_{0} q$ 是 $a_{1}, \cdots, a_{s}$的公倍数， 因 $M_{0}$ 是最小的正公倍数， 故 $r=0, M_{0} \mid M$.

  (2) 等式右边是 $\left[a_{1}, \cdots, a_{s-1}\right]$ 和 $a_{s}$ 的公倍， 前者又是 $a_{1}, \cdots, a_{s-1}$ 的公倍， 故右边是 $a_{1}, \cdots, a_{s}$ 的公倍， 从而知右边是左边 (最小公倍数) 的倍数。 另一方面， 左边是 $a_{1}, \cdots, a_{s-1}$ 的公倍， 故是 $\left[a_{1}, \cdots, a_{s-1}\right]$ 的倍数， 故左边是 $\left[a_{1}, \cdots, a_{s-1}\right]$ 与 $a_{s}$ 的公倍数， 故左边是右边的倍数。 于是知道， 左、右边互为倍数， 又都是正整数， 故左边等于右边。
\end{proof*}

\pause
\begin{proof*}[定理2的证明]
  整数唯一析因定理 (定理 1) 将整除关系化为素因子的指数大小关系，即
\[
d \mid n \Leftrightarrow v_{p}(d) \leqslant v_{p}(n) \text { (对任意正素数 $p$). }
\]
故 $d$ 是 $m, n$ 的公因子意味着 $v_{p}(d) \leqslant \min \left\{v_{p}(m), v_{p}(n)\right\}$ (对任意正素数 $p$),
所以 $d$ 是 $m, n$ 的最大公因子相当于上式等号成立， 即 $d_{p}=\min \left\{u_{p}, v_{p}\right\}$ (对任意正素数 $p$). 同理， $M$ 是 $m, n$ 的公倍数意味着 $v_{p}(M) \geqslant \max \left\{v_{p}(m), v_{p}(n)\right\}$,而 $M=[m, n]$ 意味着等号成立， 即 $M_{p}=\max \left\{u_{p}, v_{p}\right\}$ (对任意正素数 $p$ ). 进而易知 $(m, n)[m, n]=|m n|$, 因为
\[
  d_{p}+M_{p}=\min \left\{u_{p}, v_{p}\right\}+\max \left\{u_{p}, v_{p}\right\}=u_{p}+v_{p}.
\]
\end{proof*}

  \end{frame}


\begin{frame}
    在定理 1 后， 我们用 $v_{p}(n)$ 表示
  使 $p^{k} \mid n$ 的最大非负整数 $k$.
  此 $v_{p}(n)$ 称为 $n$ 的 \emph{$p$-进 (指数) 赋值} ($p$-adic exponential valuation), 是很重要的现代数学概念。 (也有人称 $v_{p}(n)$ 为素数 $p$ 在 $n$ 中的指数或阶。读者要区别其与第三章 \S3.2, \S3.3 中群与元素的阶或指数。)

~

\pause
  正合数 $n$ 的最小正素因子 $p_{0}$ 必满足
\[
p_{0} \leqslant \sqrt{n}
\]
这是因为 $n=p_{0} q, p_{0} \leqslant q$ (因 $n$ 的正素因子都大于或等于 $p_{0}$ ). 例如， 若欲分解 100 以内的整数， 则只需先用 $2,3,5,7$ 试除之即可。

\pause
虽然整数相乘容易， 但反之将大整数分解则常常较困难， 这被用于信息加密和破密。 类似的， 求各种大素数也很有意义。

\pause
\begin{comment*}%评述
这三节内容都源自 Euclid 的《几何原本》. 始于整数的带余除法， 进而辗转相除， 得出最大公因子及 Bézout 等式， 最后推知唯一析因定理。 这一思路也将被用于其他对象 (所谓 Euclid 环。 将在 §5.3, §7.1 看到， Gauss (高斯)整数、Eisenstein(艾森斯坦)整数， 皆循此路径). 由于唯一分解定理， 一个整数可被视为一抔圆珠 (素数), 这使问题极易处理。 发展开去， 人类考察任意对象时，总是先将其分解。 论者单道这“分解之妙”曰：
\begin{poem}
混沌盘古辟地天，氢氮锂铍始分辨。\\
从此万物抔圆珠， 数家分合任把玩。
\end{poem}
\end{comment*}\end{frame}

\begin{frame}{小结}

  \begin{enumerate}
    \item 叙述算术基本定理（惟一因子分解定理）。
    \item 何为素数$p$在非零整数$n$中的指数$v_p(n)$ (亦称为$n$的$p$-进赋值)? 有何性质？
    \item 如何通过$p$进赋值$v_p$来判断整除性？
    \item 何为最小公倍？有素因子分解时如何给出最大公因子和最小公倍？
    \item 试证明素数有无限多个。
  \end{enumerate}
  
\end{frame}
